package com.zhzh.sc.demo.leetcode.learn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * algorithm
 *
 * @author: insightz
 * @date: 2021-02-22 15:32
 **/
public class FunWithArrays {

    public static void main(String[] args) {
//        System.out.println("findMaxConsecutiveOnes=" + findMaxConsecutiveOnes(new int[]{1, 1, 0, 1, 1, 1}));
//        System.out.println("findNumbers=" + findNumbers(new int[]{12, 345, 2, 6, 7896}));
//        System.out.println("sortedSquares=" + Arrays.toString(sortedSquares(new int[]{-12, 0, 2, 6, 9})));
//        duplicateZeros(new int[]{-12, 0, 2, 0, 6, 9});
//        merge(new int[]{1, 2, 3, 0, 0, 0}, 3, new int[]{2, 5, 6}, 3);
//        System.out.println(removeElement(new int[]{1, 2, 3, 3, 4, 2, 3}, 3));
//        System.out.println(removeDuplicates(new int[]{1, 2, 3, 3, 4, 2, 3}));
//        System.out.println(checkIfExist(new int[]{-2, 0, 10, -19, 4, 6, -8}));
//        System.out.println(validMountainArray(new int[]{-2, 0, 3, 3, 4, 6, 8}));
//        System.out.println(Arrays.toString(replaceElements(new int[]{17,18,5,4,6,1})));
//        moveZeroes(new int[]{17, 0, 18, 5, 4, 6, 1});
//        System.out.println(Arrays.toString(sortArrayByParity(new int[]{17, 0, 18, 5, 4, 6, 1})));
//        System.out.println(heightChecker(new int[]{1, 1, 4, 2, 1, 3}));
//        System.out.println(thirdMax(new int[]{1, 1, 2}));
        System.out.println(findDisappearedNumbers(new int[]{}));

    }

    /**
     * Max Consecutive Ones
     * https://leetcode.com/explore/learn/card/fun-with-arrays/521/introduction/3238/
     *
     * @param nums
     * @return
     */
    public static int findMaxConsecutiveOnes(int[] nums) {

        int count = 0;
        int maxCount = 0;
        for (int i : nums) {
            if (i == 0) {
                count = 0;
            } else {
                count++;
            }
            if (count > maxCount) {
                maxCount = count;
            }
        }

        return maxCount;
    }

    /**
     * Find Numbers with Even Number of Digits
     * https://leetcode.com/explore/learn/card/fun-with-arrays/521/introduction/3237/
     *
     * @param nums
     * @return
     */
    public static int findNumbers(int[] nums) {
        AtomicInteger count = new AtomicInteger();
        Arrays.stream(nums).forEach(i -> {
            int length = String.valueOf(i).length();
            if (length % 2 == 0) {
                count.getAndIncrement();
            }
        });
        return count.get();
    }

    /**
     * Squares of a Sorted Array
     * https://leetcode.com/explore/learn/card/fun-with-arrays/521/introduction/3240/
     *
     * @param nums
     * @return
     */
    public static int[] sortedSquares(int[] nums) {
        int[] result = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            result[i] = nums[i] * nums[i];
        }
        Arrays.sort(result);
        return result;
    }

    /**
     * Duplicate Zeros
     * https://leetcode.com/explore/learn/card/fun-with-arrays/525/inserting-items-into-an-array/3245/
     *
     * @param arr
     */
    public static void duplicateZeros(int[] arr) {
        int[] temp = new int[arr.length];
        System.arraycopy(arr, 0, temp, 0, arr.length);
        System.out.println(Arrays.toString(temp));
        int offSet = 0;
        for (int i = 0; i < temp.length; i++) {
            if (i + offSet > temp.length - 1 || i + 1 > temp.length - 1) {
                break;
            }
            if (temp[i] == 0) {
                arr[i + offSet] = 0;
                if (i + offSet + 1 < temp.length) {
                    arr[i + offSet + 1] = 0;
                }
                offSet++;
            } else {
                arr[i + offSet] = temp[i];
            }
        }
        System.out.println(Arrays.toString(arr));
    }

    /**
     * Merge Sorted Array
     * https://leetcode.com/explore/learn/card/fun-with-arrays/525/inserting-items-into-an-array/3253/
     *
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        for (int i = 0; i < n; i++) {
            nums1[m + i] = nums2[i];
        }
        Arrays.sort(nums1);
        System.out.println("merge=" + Arrays.toString(nums1));
    }

    /**
     * Remove Element
     * https://leetcode.com/explore/learn/card/fun-with-arrays/526/deleting-items-from-an-array/3247/
     *
     * @param nums
     * @param val
     * @return
     */
    public static int removeElement(int[] nums, int val) {
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            if (nums[i] == val && i + 1 <= len) {
                if (len - 1 - i >= 0) System.arraycopy(nums, i + 1, nums, i, len - 1 - i);
                len--;
                i--;
            }
        }
        System.out.println("removeElement=" + Arrays.toString(nums));
        return len;
    }

    /**
     * Remove Duplicates from Sorted Array
     * https://leetcode.com/explore/learn/card/fun-with-arrays/526/deleting-items-from-an-array/3248/
     *
     * @param nums
     * @return
     */
    public static int removeDuplicates(int[] nums) {
        int index = 0, len = nums.length, preNum = -99999;
        for (int i = 0; i < nums.length; i++) {
            if (preNum == nums[i]) {
                len--;
            } else {
                nums[index] = nums[i];
                preNum = nums[i];
                index++;
            }
        }
        System.out.println("removeDuplicate" + Arrays.toString(nums));
        return len;
    }

    /**
     * Check If N and Its Double Exist
     * https://leetcode.com/explore/learn/card/fun-with-arrays/527/searching-for-items-in-an-array/3250/
     *
     * @param arr
     * @return
     */
    public static boolean checkIfExist(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                if (i != j && arr[i] == 0 && arr[j] == 0) {
                    return true;
                }
                if (i == j || arr[j] == 0) {
                    continue;
                }
                if (arr[i] == arr[j] * 2) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * Valid Mountain Array
     * https://leetcode.com/explore/learn/card/fun-with-arrays/527/searching-for-items-in-an-array/3251/
     *
     * @param arr
     * @return
     */
    public static boolean validMountainArray(int[] arr) {
        if (arr.length < 3) return false;
        if (arr[0] > arr[1]) return false;

        boolean peakDirect = true;
        int len = arr.length;
        for (int i = 0; i < len - 1; i++) {
            if (i != 0 && arr[i] > arr[i + 1]) {
                peakDirect = false;
            }
            if (arr[i] == arr[i + 1]) {
                return false;
            }
            if (peakDirect && arr[i] > arr[i + 1]) {
                return false;
            }
            if (!peakDirect && arr[i] < arr[i + 1]) {
                return false;
            }
        }
        return !peakDirect;
    }

    /**
     * Replace Elements with Greatest Element on Right Side
     * https://leetcode.com/explore/learn/card/fun-with-arrays/511/in-place-operations/3259/
     *
     * @param arr
     * @return
     */
    public static int[] replaceElements(int[] arr) {
        int tempMax = arr[arr.length - 1];
        for (int i = arr.length - 1; i >= 0; i--) {
            if (i == 0) {
                arr[0] = tempMax;
                break;
            }
            if (arr[i] > tempMax) {
                int tmp = tempMax;
                tempMax = arr[i];
                arr[i] = tmp;
            } else {
                arr[i] = tempMax;
            }
        }
        arr[arr.length - 1] = -1;
        return arr;
    }

    /**
     * Move Zeroes
     * https://leetcode.com/explore/learn/card/fun-with-arrays/511/in-place-operations/3157/
     *
     * @param nums
     */
    public static void moveZeroes(int[] nums) {
        int zeroCount = 0;
        int idx = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                zeroCount++;
            } else {
                nums[idx] = nums[i];
                idx++;
            }
        }
        Arrays.fill(nums, nums.length - zeroCount, nums.length, 0);
        System.out.println(Arrays.toString(nums));
    }

    public static int[] sortArrayByParity(int[] A) {
        int[] B = new int[A.length];
        int evenCount = 0;
        int oddCount = 0;
        int idx = 0;
        for (int i = 0; i < A.length; i++) {
            if (A[i] % 2 == 0) {
                A[idx] = A[i];
                idx++;
                oddCount++;
            } else {
                B[evenCount] = A[i];
                evenCount++;
            }
        }
        if (evenCount >= 0) System.arraycopy(B, 0, A, oddCount, evenCount);
        return A;
    }

    /**
     * Height Checker
     * https://leetcode.com/explore/learn/card/fun-with-arrays/523/conclusion/3228/
     *
     * @param heights
     * @return
     */
    public static int heightChecker(int[] heights) {
        int[] temp = heights.clone();
        Arrays.sort(temp);
        int optCount = 0;
        for (int i = 0; i < heights.length; i++) {
            if (heights[i] != temp[i]) optCount++;
        }
        System.out.println(Arrays.toString(heights));
        return optCount;
    }

    /**
     * Third Maximum Number
     * https://leetcode.com/explore/learn/card/fun-with-arrays/523/conclusion/3231/
     *
     * @param nums
     * @return
     */
    public static int thirdMax(int[] nums) {
        long a = Long.MIN_VALUE, b = Long.MIN_VALUE, c = Long.MIN_VALUE;
        for (int i : nums) {
            if (i > a) {
                c = b;
                b = a;
                a = i;
            } else if (i > b && i != a) {
                c = b;
                b = i;
            } else if (i > c && i != b && i != a) {
                c = i;
            }
        }
        return Long.MIN_VALUE == c ? (int) a : (int) c;
    }

    /**
     * Find All Numbers Disappeared in an Array
     * https://leetcode.com/explore/learn/card/fun-with-arrays/523/conclusion/3270/
     *
     * @param nums
     * @return
     */
    public static List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> result = new ArrayList<>();
        if (nums == null || nums.length == 0) return result;
        Arrays.sort(nums);
        if (nums[0] > 1) {
            for (int j = 1; j < nums[0]; j++) {
                result.add(j);
            }
        }

        for (int i = 0; i < nums.length - 1; i++) {
            int begin = nums[i];
            int end = nums[i + 1];
            if (end - begin > 1) {
                for (int j = begin + 1; j < end; j++) {
                    result.add(j);
                }
            }
        }
        if (nums[nums.length - 1] < nums.length) {
            for (int j = nums[nums.length - 1] + 1; j <= nums.length; j++) {
                result.add(j);
            }
        }
        return result;
    }

}
